import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-17
 * Time: 23:32
 */
public class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        temp.add(0);
        dfs(ans, temp, graph, 0);
        return ans;
    }

    public void dfs(List<List<Integer>> ans, List<Integer> temp,
                    int[][] graph, int node) {
        if (node == graph.length - 1) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < graph[node].length; i++) {
            temp.add(graph[node][i]);
            dfs(ans, temp, graph, graph[node][i]);
            temp.remove(temp.size()-1);
        }
    }
}
